package algorithm;

import java.util.Arrays;

/**
 * @author: vince_zww
 * @date: 2019/9/9 19:05
 * @desceription: 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int a[]={99,9,6,8,10,2,5,3,4,7,12,15,48,78,95,35,23,29,98,19};

        long quickSortStartTime = System.nanoTime();
        System.out.println(Arrays.toString(quickSort(a,0,a.length-1)));
        long quickSortEndTime = System.nanoTime();
        System.out.println("快速排序运行时间："+(quickSortEndTime-quickSortStartTime)+"ns");

    }
    /**
     * 快速排序
     */
    public static int[] quickSort(int[] array,int start,int end){
        if(array.length < 1 || start<0 || end >= array.length || start>end){
            return null;
        }
        int smallIndex = partition(array,start,end);
        if (smallIndex > start){
            quickSort(array,start,smallIndex-1);
        }
        if (smallIndex < end){
            quickSort(array,smallIndex+1,end);
        }

        return array;
    }

    /**
     * 快速排序算法——partition
     */
    private static int partition(int[] array,int start,int end){
        //取最后一个数为基准
        int pivot = end;
        int smallIndex = start-1;
        for (int i = start; i <= end; i++) {
            if (array[i]<=array[pivot]){
                smallIndex++;
                if(i>smallIndex){
                    swap(array,i,smallIndex);
                }
            }
        }
        return smallIndex;
    }

    /**
     * 交换数组内两个元素
     */
    public static void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }

}
